package algorithm.tree;

public class BinarySearch {


    public static int search(Integer[] array, Integer item) {

        int l = 0;
        int r = array.length - 1;
        while (l <= r) {
            int middle = l + (r - l) / 2;
            if (array[middle].equals(item)) {
                return middle;
            }
            if (array[middle] < item) {
                l = middle + 1;
            } else {
                r = middle - 1;
            }
        }
        return -1;
    }


    public static int searchRecursion(Integer[] array, Integer item) {
        return search(array, item, 0, array.length - 1);
    }


    public static int search(Integer[] array, Integer item, int l, int r) {
        if (l >= r) {
            return -1;
        }
        int middle = l + (r - l) / 2;
        if (array[middle].equals(item)) {
            return middle;
        } else if (array[middle] > item) {
            r = middle - 1;
        } else {
            l = middle + 1;
        }
        return search(array, item, l, r);
    }

    public static void main(String[] args) {
        int N = 5;
        Integer[] arr = new Integer[N];
        for (int i = 0; i < N; i++)
            arr[i] = new Integer(i);
        // 对于我们的待查找数组[0...N)
        // 对[0...N)区间的数值使用二分查找，最终结果应该就是数字本身
        // 对[N...2*N)区间的数值使用二分查找，因为这些数字不在arr中，结果为-1
        int a = BinarySearch.search(arr, new Integer(3));
        int b = BinarySearch.searchRecursion(arr, new Integer(3));
        System.out.println(a);
        System.out.println(b);

        return;
    }

}
